package m202405.d25;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/25 17:36
 */
public class Q79 {

    public static void main(String[] args) {
        Q79 q79 = new Q79();
        q79.exist(new char[][]{
                {'a', 'b'},
                {'c', 'd'}
        }, "cdba");

    }

    public boolean exist(char[][] board, String word) {
        if (word.length() > board.length * board[0].length) {
            return false;
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == word.charAt(0) && exit(board, word, 0, i, j, new boolean[board.length][board[i].length])) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean exit(char[][] board, String word, int index, int row, int col, boolean[][] flag) {
        if (index == word.length()) {
            return true;
        }
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
            return false;
        }
        if (flag[row][col]) {
            return false;
        }
        if (board[row][col] != word.charAt(index)) {
            return false;
        }
        flag[row][col] = true;
        boolean rs = exit(board, word, index + 1, row - 1, col, flag)
                || exit(board, word, index + 1, row + 1, col, flag)
                || exit(board, word, index + 1, row, col + 1, flag)
                || exit(board, word, index + 1, row, col - 1, flag);
        if (!rs) {
            flag[row][col] = false;
        }
        return rs;
    }
}
